class BinaryTree
	attr_accessor :root

	def initialize(element,type)
		@root = BinaryNode.new(element,type)
	end
	
	def to_s
		return @root.to_s
	end
	
	def to_svg
    	return "<?xml version='1.0' encoding='ISO-8859-1'?><svg xmlns='http://www.w3.org/2000/svg' onload='alert(\'hi\');'>" + @root.to_xml + "</svg>"
  	end

	def self.remove element
		return @root.remove(element,nil,self)
	end
	
	def removeSelects
		@root.left= @root.left.left
	end
	
	def grabTables
		@root.grabTables []
	end
	
	def insertSelectPredicate element
		@root.insertSelectPredicate element,nil
	end
	
	def insertJoinPredicate element
		@root.insertJoinPredicate element, nil
	end

	def insertProject element
		@root.left.insertProject element, nil, nil
	end
	
	def mergeJoins
		return @root.left.merge @root
	end

	def tableScan
		return @root.left.tableScan @root
	end

	def joinScan
		return @root.left.joinScan
	end
end

class BinaryNode
	attr_accessor :element, :left, :right, :type, :optimizer

	def initialize(element,new_type)
		@element = element
		@left =  nil
		@right = nil
		@type = new_type
		@optimizer = nil
	end
	
	def tableScan(parent)
		if @type == "TABLE"
			#do stuff
			if parent.type == "SELECT"
				#do stuff
				parent.optimizer= "scan on clustering index"
				@optimzer= "file scan"
			else
				#do stuff
				@optimizer = "file scan"
			end
		else
			if @left
				@left.tableScan(self)
			end
			
			if @right
				@right.tableScan(self)
			end
		end
	end

	def hasSelectAttribute(ele)
		if @type == "TABLE"
			e = ele.split("=")
			if @element.split("=")[0].eql?(e[0]) or @element.split("=")[0].eql?(e[1])
				return true
			else
				return false
			end
		else
			leftBool = false
			if @left
				bool = @left.hasSelectAttribute(ele)
			end
			
			rightBool = false
			if @right
				bool = @right.hasSelectAttribute(ele)
			end
			
			return (leftBool or rightBool)
		end
	end

	def joinScan
		if @type == "CROSS"
			#do stuff
			@type = "JOIN"
			if @element == ""
				@optimizer = "nested-loop join"
			else
				if @left.hasSelectAttribute(@element) and @right.hasSelectAttribute(@element)
					@optimizer = "sort-merge join"
				else
					@optimizer = "single-loop join"
				end
			end
			
			if @left
				@left.joinScan
			end
			
			if @right
				@right.joinScan
			end
		else
			if @left
				@left.joinScan
			end

			if @right
				@right.joinScan
			end
		end
	end
	
	def insertProject(element,parent,additional_info)
		if @type == "TABLE"
			#do stuff
			if self.grabColumns([]).include?(element)
				if parent.type == "PROJECT"
					parent.element= parent.element + "," + element
				else
					#time to prune
					for x in additional_info
						if self.grabColumns([]).include?(x)
							element += "," + x
						end
					end

					temp = BinaryNode.new(element,"PROJECT")
					temp.left= self
					if parent.right == self
						parent.right= temp
					else
						parent.left= temp
					end
				end
			end
		elsif @type == "CROSS"
			if not @element.eql? ""
				if not additional_info
					additional_info = []
				end

				additional_info << @element.split("=")[0]
				additional_info << @element.split("=")[1]

				@left.insertProject(element,self,additional_info)
				@right.insertProject(element,self,additional_info)
			end
		elsif @type == "SELECT"
			if not additional_info
				additional_info = []
			end
			
			additional_info << @element.split("=")[0]
			
			@left.insertProject(element,self,additional_info)
		else
			if @left
				@left.insertProject(element,self,additional_info)
			end
			
			if @right
				@right.insertProject(element,self,additional_info)
			end
		end
	end
	
	def merge(parent)
		if @type == "SELECT"
			if @left.type == "CROSS"
				@left.element= @element
				if parent.right == self
					parent.right= @left
				else
					parent.left= @left
				end
			else
				if @left
					@left.merge self
				end
				
				if @right
					@right.merge self
				end
			end
		else
			if @left
				@left.merge self
			end

			if @right
				@right.merge self
			end
		end
	end
	
	def grabTable
		if @type == "TABLE"
			return self
		else
			return @left.grabTable
		end
	end
	
	def grabTables list
		if @type == "PROJECT"
			if @left
				return @left.grabTables list
			end			
			return list
		elsif @type == "CROSS"
			list = @right.grabTables list
			list = @left.grabTables list
			return list
		elsif @type == "TABLE"
			return list << self
		elsif @type == "SELECT"
			return list << self
		end
	end
	
	def grabColumns list
		if @type == "TABLE"
			col = COLUMNS.find(:all, :conditions => ["TABLE_NAME ='" + @element + "'"])
			for z in col
				list << z.COLUMN_NAME
			end
		else
			if @left
				@left.grabColumns list
			end
			
			if @right
				@right.grabColumns list
			end
		end
		return list
	end
	
	def insertJoinPredicate element, parent
		if @type == "CROSS"
			rightTablePreds = []
			leftTablePreds = []
			rightTablePreds = @right.grabColumns(rightTablePreds)
			leftTablePreds = @left.grabColumns(leftTablePreds)
			if 	(rightTablePreds.include?(element.split("=")[0]) and leftTablePreds.include?(element.split("=")[1]) ) or
					(rightTablePreds.include?(element.split("=")[1]) and leftTablePreds.include?(element.split("=")[0]) )
					temp = BinaryNode.new(element, "SELECT")
					parent.left= temp
					temp.left= self
			end
		else
			if @left
				@left.insertJoinPredicate element,self
			end

			if @right
				@right.insertJoinPredicate element,self
			end
		end
	end
	
	def insertSelectPredicate element,parent
		if @type == "TABLE"
			tablesPreds = []
			col = COLUMNS.find(:all, :conditions => ["TABLE_NAME = '" + @element + "'"])
			for z in col
				tablesPreds << z.COLUMN_NAME
			end
			if tablesPreds.include?(element.split("=")[0])
				temp = BinaryNode.new(element, "SELECT")
				if parent.right == self
					parent.right= temp
					temp.left= self
				else
					parent.left= temp
					temp.left= self
				end
			end
		else
			if @left
				@left.insertSelectPredicate element,self
			end

			if @right
				@right.insertSelectPredicate element,self
			end
		end
	end

	def to_s
		s = "(" + @type + " (" + @element

		if @additional_info
			s += "," + @additional_info
		end

		s += ")"

		if @optimizer
			s += " (" + @optimizer + ")"
		end

		if @left
			s += " " + @left.to_s
		end
		
		if @right
			s += " " + @right.to_s
		end
		
		return s + ")"
	end
	
	def to_xml
  	  xml = "<g><text style='text-anchor:middle;font-family:Lucida Console Unicode, Arial, Helvetica, Serif;font-size:20px;'>" + @type + " (" + @element

  	  if @additional_info
  			xml += "," + @additional_info
  		end

  		xml += ")"

  		if @optimizer
  			xml += " (" + @optimizer + ")"
  		end

      xml += "</text><line style='stroke:black;'/>"
      
  		if @left
  			xml += @left.to_xml
  		end

  		if @right
  			xml += @right.to_xml
  		end

  		return xml + "</g>"
  end

	def self.remove(element_to_remove,parent,binary_tree)
		if @element.eql?(element_to_remove)
			if parent == nil
				binary_tree.root= @left
			else
				if @left == parent.left
					parent.left= @left
				else
					parent.right= @left
				end
			end
		end
	end

end